package offer.tree;

import java.util.Stack;

/**
 * @author DengYuan2
 * @create 2021-03-02 18:56
 */
public class n_54 {
    public static void main(String[] args) {
        n_54 n = new n_54();
        TreeNode t1 = new TreeNode(5);
        TreeNode t2 = new TreeNode(3);
        TreeNode t3 = new TreeNode(7);
        TreeNode t4 = new TreeNode(2);
        TreeNode t5 = new TreeNode(4);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(8);
        t1.left=t2;
        t1.right=t3;
        t2.left=t4;
        t2.right=t5;
        t3.left=t6;
        t3.right=t7;
        TreeNode res = n.KthNode2(t1, 4);
        System.out.println(res);
    }

    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot==null){
            return null;
        }
        int count=0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur =pRoot;
        while (cur!=null || !stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode pop = stack.pop();
            count++;
            if (count==k){
                return pop;
            }
            cur=pop.right;
        }
        return null;
    }

    /**
     * 大神写法
     * @param pRoot
     * @param k
     * @return
     */
    int count =0;
    TreeNode res=null;
    TreeNode KthNode2(TreeNode pRoot, int k) {
        if (pRoot==null){
            return null;
        }
        helper(pRoot,k);
        return res;
    }

    void helper(TreeNode node,int k){
        if (node==null || count>=k){
            return;
        }
        helper(node.left,k);
        count++;
        if (count==k){
            res=node;
        }
        helper(node.right,k);
    }

}
